#pragma once
#include <algorithm>
#include <vector>
#include <string>
#include <cassert>
#include <iostream>
#include <unistd.h>
#include <list>

namespace STL
{
    enum State
    {
        EXIST,
        EMPTY,
        DELETE
    };

    template <class K, class V>
    struct HashData
    {
        std::pair<K, V> _kv;
        State _state = EMPTY;
    };

    template <class K>
    struct HashFunc
    {
        size_t operator()(const K &key)
        {
            return (size_t)key;
        }
    };

    template <>
    struct HashFunc<std::string>
    {
        size_t operator()(const std::string &key)
        {
            size_t skey = 0;
            for (const auto &x : key)
            {
                skey *= 131;
                skey += x;
            }
            return skey;
        }
    };

    template <>
    struct HashFunc<int>
    {
        size_t operator()(const int &key)
        {
            return (key >> 16) ^ key;
        }
    };
    namespace KSHash
    {
        template <class K, class V>
        class HashTable
        {
        public:
            HashTable()
            {
                _tables.resize(__stl_next_prime(_tables.size()));
            }

            HashData<K, V> *Find(const K &key)
            {
                if (_tables.empty())
                    return nullptr;

                HashFunc<K> hs;
                size_t start = hs(key) % _tables.size();
                size_t hashi = start;
                size_t i = 0;

                // 添加循环次数限制，防止死循环
                while (i < _tables.size())
                {
                    if (_tables[hashi]._state == EMPTY)
                    {
                        return nullptr;
                    }
                    else if (_tables[hashi]._state == EXIST)
                    {
                        if (_tables[hashi]._kv.first == key)
                        {
                            return &_tables[hashi];
                        }
                    }
                    // 对于DELETE状态，继续查找

                    // 线性探测
                    hashi = (start + ++i) % _tables.size();
                }

                return nullptr; // 遍历完整个表都没找到
            }

            bool Erase(const K &key)
            {
                HashData<K, V> *ret = Find(key);
                if (ret == nullptr)
                    return false;
                else
                {
                    ret->_state = DELETE;
                    _n -= 1;
                    return true;
                }
            }

            int size()
            {
                return _n;
            }

            bool Insert(const std::pair<K, V> &kv)
            {
                if (Find(kv.first) != nullptr)
                    return false;
                // std::cout << "ok" << std::endl;
                if (_n * 10 / _tables.size() >= 7)
                {
                    HashTable tmp;
                    tmp._tables.resize(_tables.size() + 1);
                    for (size_t i = 0; i < _tables.size(); i++)
                    {
                        tmp.Insert(_tables[i]._kv);
                    }
                    _tables.swap(tmp._tables);
                    _n = tmp._n;
                }

                HashFunc<K> hs;
                size_t hashi = hs(kv.first) % _tables.size();
                while (_tables[hashi]._state != EMPTY)
                {
                    hashi += 1;
                    hashi %= _tables.size();
                }
                _tables[hashi]._kv = kv;
                _tables[hashi]._state = EXIST;
                _n += 1;
                return true;
            }

            inline unsigned long __stl_next_prime(unsigned long n)
            {
                static const int __stl_num_primes = 28;
                static const unsigned long __stl_prime_list[__stl_num_primes] = {
                    53, 97, 193, 389, 769,
                    1543, 3079, 6151, 12289, 24593,
                    49157, 98317, 196613, 393241, 786433,
                    1572869, 3145739, 6291469, 12582917, 25165843,
                    50331653, 100663319, 201326611, 402653189, 805306457,
                    1610612741, 3221225473, 4294967291};
                const unsigned long *first = __stl_prime_list;
                const unsigned long *last = __stl_prime_list + __stl_num_primes;
                const unsigned long *pos = std::lower_bound(first, last, n);
                return pos == last ? *(last - 1) : *pos;
            }

        private:
            std::vector<HashData<K, V>> _tables;
            size_t _n = 0;
        };
    }

    namespace BSHash
    {
        template <class K, class V>
        class HashTable
        {
            using DataList = std::list<std::pair<K, V>>;
            using iterator = typename std::list<std::pair<K, V>>::iterator;

        public:
            HashTable(size_t n = 0)
                : _n(0)
            {
                _tables.resize(__stl_next_prime(n));
            }
            // void resize(size_t n)
            // {
                
            // }
            size_t TableSize()
            {
                return _tables.size();
            }

            size_t Size()
            {
                return _n;
            }
            bool Erase(const K &key)
            {
                std::pair<iterator, bool> ret = Find(key);
                if (ret.second == false)
                    return false;
                HashFunc<K> hf;
                size_t hashi = hf(key) % _tables.size();
                _tables[hashi].erase(ret.first);
                --_n;
                return true;
            }

            // 返回目标的迭代器
            std::pair<iterator, bool> Find(const K &key)
            {
                HashFunc<K> hf;
                size_t hashi = hf(key) % _tables.size();
                DataList &dlist = _tables[hashi];

                for (auto it = dlist.begin(); it != dlist.end(); it++)
                {
                    if (it->first == key)
                        return {it, true};
                }
                return {dlist.end(), false};
            }

            bool Insert(const std::pair<K, V> &data)
            {
                if (Find(data.first).second == true)
                    return false;
                if (_n * 10 >= _tables.size() * 7)
                {
                    HashTable tmp(_tables.size() + 1);
                    for (size_t i = 0; i < _tables.size(); i++)
                    {
                        for (const auto &it : _tables[i])
                        {
                            tmp.Insert(it);
                        }
                    }
                    _tables.swap(tmp._tables);
                }
                HashFunc<K> hf;
                size_t hashi = hf(data.first) % _tables.size();
                _tables[hashi].push_front(data);
                ++_n;
                return true;
            }

            void Print() const
            {
                std::cout << "Hash Table (size: " << _tables.size() << ", elements: " << _n << "):\n";
                for (size_t i = 0; i < _tables.size(); ++i)
                {
                    std::cout << "[" << i << "]: ";
                    if (_tables[i].empty())
                    {
                        std::cout << "empty";
                    }
                    else
                    {
                        for (const auto &kv : _tables[i])
                        {
                            std::cout << "{" << kv.first << ":" << kv.second << "} ";
                        }
                    }
                    std::cout << std::endl;
                }
                std::cout << "-------------------\n";
            }

        private:
            inline unsigned long __stl_next_prime(unsigned long n)
            {
                static const int __stl_num_primes = 28;
                static const unsigned long __stl_prime_list[__stl_num_primes] = {
                    53, 97, 193, 389, 769,
                    1543, 3079, 6151, 12289, 24593,
                    49157, 98317, 196613, 393241, 786433,
                    1572869, 3145739, 6291469, 12582917, 25165843,
                    50331653, 100663319, 201326611, 402653189, 805306457,
                    1610612741, 3221225473, 4294967291};
                const unsigned long *first = __stl_prime_list;
                const unsigned long *last = __stl_prime_list + __stl_num_primes;
                const unsigned long *pos = std::lower_bound(first, last, n);
                return pos == last ? *(last - 1) : *pos;
            }

        private:
            std::vector<DataList> _tables;
            size_t _n;
        };
    }
}